package arithmetic;

import leetcode.editor.cn.ImplementTriePrefixTree208;

/**
 * @author Ajie
 * @date 2024/4/10
 * @function
 */
public class Trie_a {

    TrieNode root = new TrieNode();//与上面是相等的，每次，引用this.

    class TrieNode{
        //not have val . son[n] !=null就是 value  son[n] ==null.
        boolean isEnd;
        TrieNode[] son = new TrieNode[26];
    }

    public void insert(String word) {
        if (word == null || word.length()<1)return;
        TrieNode cur = root;
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int sonIndex = chars[i] - 'a';
            TrieNode sonV = cur.son[sonIndex];
            if (sonV == null){
                cur.son[sonIndex] = new TrieNode();
            }
            cur = cur.son[sonIndex];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode trieNode = startPrefix(word);
        return trieNode!=null && trieNode.isEnd;
    }

    public boolean startsWith(String prefix) {
        return startPrefix(prefix)!=null;
    }

    public TrieNode startPrefix(String prefix) {
        if (prefix == null || prefix.length()<1) return null;
        TrieNode curNode = root;
        char[] chars = prefix.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int sonIndex = chars[i] - 'a';
            TrieNode sonNode = curNode.son[sonIndex];
            if (sonNode == null)return null;
            curNode = sonNode;
        }
        return curNode;
    }
}
